Pour compiler ce document en présentation, exécuter :
jupyter nbconvert Cours\ d’algorithmique.ipynb --to slides --post serve
Algorithme = suite logique d’instructions précises permettant de résoudre un problème à partir de données.
Algorithmique = science et art de structurer un problème complexe pour le résoudre de manière efficace et élégante.
C’est donc le point commun de tous les langages de programmation.
Fermez vos PCs, aujourd’hui on apprend à coder sur papier.
À noter :
Comme une langue :
Pas comme une langue :
Langage de programmation ≠ langage déclaratif/descriptif (SQL, HTML, CSS, LaTeX)
| Programmation | Déclaration/Description |
|---|---|
| Construis ce meuble ! | Ce meuble est bleu et un peu moche. |
Les langages de programmation contiennent souvent une partie descriptive, mais la plupart du temps il s’agit donc d’ordres.
On parle de programmation impérative lorsqu’il s’agit essentiellement ou uniquement de donner des ordres.
Pour lancer un programme en langage compilé :
En langage interprété :
Toutefois, de nombreux éléments rendent cette conclusion fausse :
| Année | Langage | |
|---|---|---|
| 1954 | FORTRAN et le premier assembleur | compilés |
| 1959 | COBOL | compilé |
| 1972 | C | compilé |
| années 1970 | disparition des cartes perforées | |
| 1991 | Python | interprété |
| 1995 | Java, Javascript et PHP | interprétés |
Tous ces langages sont encore indispensables aujourd’hui :
Et oui, les langages les plus anciens encore utilisés aujourd’hui sont en fait les plus indispensables !
Lourds calculs ou informatique embarquée ⇒ langages compilés
Pour tout le reste ⇒ langages interprétés
Ensuite, un art consistant à choisir le meilleur compromis entre :
Mes recommandations après 22 ans d’expérience sur une vingtaine de langages :
3 est une donnée. « J’aime coder » aussi.
Comment les stocker ?
Deux manières :
Il faut donner un nom, sans espaces ni caractères spéciaux, juste de l’ASCII.
Certaines données peuvent être très simples, comme un nombre.
D’autres peuvent être très complexes, comme un index de base de données sous forme d’arborescence.
Les types de base sont presque toujours les mêmes :
Booléens : uniquement True ou False
Nombres entiers : 3, -8752, 654189426871662371897286541987153419827154
Nombres à virgule (flottants) : 1.0, -5e19, 8e-20, NaN, +inf, -inf
Chaînes de caractères : 'a', 'Bonjour', 'βατρακοι'
Des tas d’autres types disponibles dans les langages : fichiers, dates, ensembles, nombres complexes, expressions régulières.
Un programme est constitué d’instructions. Exemples d’instructions :
La plupart du temps, les instructions s’exécutent en séquence. Exemple de séquence d’instructions :
In [ ]:
une_variable = 5
Cette opération d’assignation est un peu différente des autres :
| Type d’opération | Opérateur | Exemples | Résultats |
|---|---|---|---|
| Combinaison | + - * / % |
2 + 7 |
9 |
| Comparaison | == != > < >= <= |
9 == 9 |
True |
| Combinaison booléenne | and or not ou && || ! |
True and False |
False |
| Combinaison binaire | & | ^ ~ |
0b0011 & 0b1100 |
0b0000 |
Des raccourcis existent dans la plupart des langages, par exemple :
In [ ]:
x = 3
x += 7
x *= 8
Équivaut parfaitement à :
In [ ]:
x = 3
x = x + 7
x = x * 8
Définir la constante mathématique π avec une précision de 2 chiffres après la virgule.
Que vaut x après ces trois lignes ?
x = 27
x -= 2
x / 5
Tester si « é » est différent de « e ».
Définir une variable x valant 333, la diviser par 3, retirer 11 et diviser par 10.
Ceci doit être fait en deux instructions.
Combien vaut x à la fin ?
In [ ]:
int data[3] = {500, 800, 3};
data[0] // 500
float data[3][3] = {{1.0, 2.0, 3.0},
{4.0, 5.0, 6.0},
{7.0, 8.0, 9.0}};
data[1][1] // 5
Exemple Python :
In [ ]:
data = [500, 800, 3]
data[0] # 500
data = [[1.0, 2.0, 3.0],
[4.0, 5.0, 6.0],
[7.0, 8.0, 9.0]]
data[1][1] # 5
data = ['a', 1, True]
data[2] # True
In [ ]:
ages = {
'Jean-Paul': 42,
'Zoé': 12,
'Lucas': 27,
}
In [ ]:
struct Book {
char[50] title
char[50] subtitle
char[150] authors
int length
}
In [1]:
class Book:
def __init__(self, title, subtitle='', authors='', length=None):
self.title = title
self.subtitle = subtitle
self.authors = authors
self.length = length
def __str__(self):
return '« %s » par %s' % (self.title, self.authors)
print(Book('Les Piliers de la terre', authors='Ken Follet'))
La séquence est la structure de contrôle par défaut. Bien entendu, elle n’est pas pratique, on ne peut se contenter de toujours suivre le même circuit.
Il existe principalement deux autres structures de contrôle.
Si en retard, pas de petit déjeuner !
Une fois sur le lieu de travail, il faut travailler jusqu’à l’heure de sortie :
Ensuite, chez moi, je dois faire la vaisselle. On peut dire :
Mais pour être plus rapide et lisible, il est préférable de dire :
Voyons comment ceci se traduit en algorithmique.
In [ ]:
name = input('Bonjour, quel est votre nom ? ')
if name == 'Germaine':
print('Bonjour arrière-grand-mère !')
elif name == 'Jean-Marie':
print('Bonjour tonton !')
else:
print('Bonjour ' + name + ' !')
In [ ]:
x = 7
if x / 3.5 >= 2:
x += 9
if x * 3 > 17:
x /= 8
else:
x -= 2
In [ ]:
maximum = 0
for number in [7, 28, 4, 9, 12, 3]:
if number > maximum:
maximum = number
Ceci fonctionne dans quelques langages de haut niveau comme Python, mais dans la plupart des langages, il faut créer un index intermédiaire. Par exemple en C :
In [ ]:
void main() {
int maximum = 0;
int data[6] = {7, 28, 4, 9, 12, 3};
for (int i = 0; i < 6; i++) {
int number = data[i];
if (number > maximum) {
maximum = number;
}
}
}
Dans les autres cas :
In [ ]:
while input('Avez-vous fini ? ') not in ('oui', 'o', 'OUI', 'O', 'Oui'):
print('Écrivez oui, tout va bien se passer.')
Ou :
In [ ]:
while True:
if input('Avez-vous fini ? ') in ('oui', 'o', 'OUI', 'O', 'Oui'):
break
print('Écrivez oui, tout va bien se passer.')
In [ ]:
x = 0
i = 5
while i > -2:
x += i
i -= 1
In [ ]:
def function(n: int) -> int:
return n * 4 + 2
In [ ]:
def procedure(l: list):
l[0] = 3
print('Nous avons modifié la liste en entrée')
Un paradigme nommé programmation fonctionnelle consiste à n’utiliser que des fonctions et jamais de procédure. En pratique, ce paradigme est rarement utilisé seul, car il empêche toute interaction avec le système d’exploitation (et donc avec fichiers, réseaux, périphériques)
In [ ]:
def martin(first_name: str):
return first_name + ' Martin'
In [ ]:
def martin_bis():
first_name = input('Quel est votre prénom, monsieur Martin ?')
return first_name + ' Martin'
In [ ]:
def f(n: int):
print('Bonjour')
return n + 5
In [ ]:
def find_min_max(tree: list):
minimum = float('inf')
maximum = 0
for value in tree:
if isinstance(value, list):
value_min, value_max = find_min_max(value)
if value_min < minimum:
minimum = value_min
if value_max > maximum:
maximum = value_max
else:
if value < minimum:
minimum = value
if value > maximum:
maximum = value
return minimum, maximum
find_min_max([
[827, 312, [592, 522]],
910, 395, [815],
[195, 168, [806, 497, [972]]],
])
In [ ]:
def fib(i: int) -> int:
if i < 2:
return i
return fib(i-1) + fib(i - 2)
Désolé pour vous, il faut faire des efforts.
Vous devrez vous construire ces habitudes avec le temps pour être un dev de qualité supérieure :
De manière générale :
L’erreur du débutant : écrire une énorme fonction devenant incompréhensible pour une tâche globale comme mon_jeu().
Structurer son code = subdiviser une vaste tâche en tâches élémentaires, et grouper ces tâches de manière censées.
Outils à disposition :
Un module est un fichier regroupant des fonctions, des constantes, des classes, etc.
Un module peut aussi être un dossier regroupant plusieurs sous-modules et ainsi de suite.
Structurer son code permet donc de créer une arborescence de module qui soit claire pour les développeurs l’utilisant.
Librairie = module partagé par quelqu’un pour que d’autres puissent s’en servir facilement
Une librairie est généralement installée une seule fois sur le système, et plusieurs programmes peuvent s’en servir sans avoir à la réinstaller à chaque fois.
mon_jeu
lancer_jeu()afficher_bouton_quand_appuyé()jeu_video
manettes
NOMBRE_MAXIMUM_DE_MANETTESnombre_de_manettesallumer_manettes()éteindre_manettes()afficher_nom(manette)lister_boutons(manette)Manette
nomboutonsallumer()éteindre()video
Aussi appelée « architecture trois tiers »
Omniprésente en informatique aujourd’hui. Utilisée par les applications de bureau ou mobiles et sur les sites Internet.
Les couches sont :
| Couche | Site Internet | Tableur de bureau |
|---|---|---|
| Affichage | Navigateur web | Fenêtre avec cases, menus, boutons |
| Traitement | Serveur applicatif | Calcul du contenu des cellules |
| Stockage | Base de données SQL | Fichier ODS, XLS, CSV |
À retenir, ce sera le point de départ de la plupart de vos projets.
In [ ]:
def manger(bras, bouche):
lever(bras)
ouvrir(bouche)
fermer(bouche)
while est_pleine(bouche):
ouvrir(bouche)
fermer(bouche)
Ou encore :
In [ ]:
def manger(bras, bouche):
lever(bras)
while True:
ouvrir(bouche)
fermer(bouche)
if not est_pleine(bouche):
break
Évidemment, lever, ouvrir, fermer et est_pleine restent à définir.
Prenons un cas plus abstrait mais plus précis.
In [ ]:
def trouver_minimum(l):
minimum = float('+inf')
for i in l:
if i < minimum:
minimum = i
return minimum
Organigramme plus clair pour débuter, mais bien plus long et compliqué à lire quand on est habitué au code.
Ne pas hésiter à se faire des organigrammes pour mettre les choses à plat.
Oui, je m’en sers encore de temps en temps.
Sert à identifier un algorithme lent, puis à comprendre pourquoi et trouver comment l’améliorer.
On utilise la notation O() pour décrire le temps d’exécution d’une fonction ou procédure dans le pire des cas.
Pour une fonction ou procédure, on dit qu’elle est :
O(1) si elle prend toujours le même temps, quelque soit son contenu.O(n) si elle prend un temps linéairement proportionnel à la valeur d’un argumentO(2n) si elle prend un temps proportionnel à 2 fois la la valeur d’un argumentO(n²) si elle prend un temps proportionnel au carré de la valeur d’un argumentO(m×n) si elle prend un temps proportionnel au produit des valeurs de deux argumentsO(log n) si elle prend un temps logarithmiquement proportionnel à la valeur d’un argumentDe même que pour noter le pire des cas, la notation Ω() permet de décrire le meilleur des cas.
Il existe d’autres notations pour décrire d’autres complexités : la mémoire utilisée, le nombre d’opérations effectuées, etc.
In [ ]:
def f(n: int) -> int:
return 3 * n
Complexité : O(1)
In [ ]:
def f(n: int) -> int:
total = 0
for i in range(n):
total += i
return total
Complexité : O(n)
In [ ]:
def f(m: int, n: int) -> int:
total = 0
for x in range(m):
for y in range(n):
total += x * y
return total
Complexité : O(m×n)
In [ ]:
def f() -> int:
return 3
In [ ]:
def f(m: int, n: int) -> int:
total = 0
for i in range(m):
total += i * n
return total
In [ ]:
def f(n: int) -> int:
total = 1
for x in range(n):
for y in range(n):
total *= n
total /= 2
return total
Souvent les problèmes les plus simples sont les plus intéressants à étudier, car ils aboutissent à des gains de performance sur l’ensemble de l’informatique.
Exemple typique : tri d’une liste.
Opération utile partout et pourtant il est facile de la faire inefficacement.
In [1]:
DATA = [7, 10, 3, 9, 6, 0, 4, 13, 2, 12, 8, 11, 5, 1]
In [2]:
def tri(l: list) -> list:
n = len(l)
for i1 in range(n):
minimum = i1
for i2 in range(i1+1, n):
if l[i2] < l[minimum]:
minimum = i2
if minimum != i1:
l[i1], l[minimum] = l[minimum], l[i1]
return l
In [3]:
print(tri(DATA.copy()))
%timeit tri(DATA.copy())
In [4]:
def tri(l: list) -> list:
n = len(l)
for i1 in range(n):
v1 = l[i1]
i2 = i1
while i2 > 0 and l[i2 - 1] > v1:
l[i2] = l[i2 - 1]
i2 -= 1
l[i2] = v1
return l
In [5]:
print(tri(DATA.copy()))
%timeit tri(DATA.copy())
In [6]:
def descendre(l: list, premier: int, dernier: int):
maximum = 2 * premier + 1
while maximum <= dernier:
if maximum < dernier and l[maximum] < l[maximum + 1]:
maximum += 1
if l[maximum] > l[premier]:
l[maximum], l[premier] = l[premier], l[maximum]
premier = maximum
maximum = 2 * premier + 1
else:
break
def tri(l: list) -> list:
n = len(l) - 1
for i in range(int(n / 2), -1, -1):
descendre(l, i, n)
for i in range(n, 0, -1):
if l[0] > l[i]:
l[0], l[i] = l[i], l[0]
descendre(l, 0, i-1)
return l
In [7]:
print(tri(DATA.copy()))
%timeit tri(DATA.copy())
Première possibilité : nous sommes dans le pire des cas du tri par tas mais le meilleur des cas pour les autres algorithmes
Seconde possibilité : notre implémentation est trop lente.
Regardez le tri par tas, son exécution demande d’exécuter beaucoup plus d’instructions que les autres algorithmes.
Les détails d’implémentation sont très importants, c’est pourquoi l’algorithmique doit être combinée à une excellente connaissance du langage en question.
L’algorithme de tri de Python, de même complexité algorithmique :
In [8]:
l = DATA.copy()
l.sort()
print(l)
l = DATA.copy()
%timeit l.sort()